package org.atovio.structure.map;

import org.atovio.structure.adt.Map;
import org.atovio.structure.tree.BinarySortTree;
import org.atovio.structure.tree.TriNode;

/**
 * 树映射
 *
 * @author AtoVio, Winter Yuan
 * @version 1.0
 */
public class TreeMap<K extends Comparable<? super K>, V> implements Map<K, V> {

    // 使用二叉排序树存储排序集合
    private final BinarySortTree<SortedKeyValue<K, V>> set;

    // 构造空树
    public TreeMap() {
        this.set = new BinarySortTree<>();
    }

    /**
     * 获取指定关键词元素的值
     *
     * @param key 关键字
     * @return 指定关键词的值
     */
    @Override
    public V get(K key) {
        SortedKeyValue<K, V> kv = new SortedKeyValue<>(key, null);
        TriNode<SortedKeyValue<K, V>> target = this.set.searchNode(kv);
        return target != null ? target.data.value : null;
    }

    /**
     * 添加元素。若是重复关键字，替换映射值
     * @param key 关键字
     * @param value 映射值
     * @return true
     */
    @Override
    public boolean put(K key, V value) {
        SortedKeyValue<K, V> kv = new SortedKeyValue<>(key,value);
        if (!this.set.add(kv))
            this.set.searchNode(kv).data.value = value;
        return true;
    }

    /**
     * 删除关键字为key的元素
     * @param key 关键字
     * @return 元素的映射值
     */
    @Override
    public V remove(K key) {
        return this.set.remove(new SortedKeyValue<>(key, null)).value;
    }


    public void inOrder() {
        this.set.inOrder();
    }
}
